home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / oper_sys / presto / prest1_0.lha / Tests / sos / sos.C < prev   
C/C++ Source or Header  |  1991-12-11  |  3KB  |  164 lines
  1. //
  2. // This is a C++/Presto program to solve the sum-of-subsets problem
  3. // using a parallel version of the backtracking algorithm described
  4. // in Horowitz and Sahni.  There is clearly something wrong with the
  5. // policy for starting new threads since the speedup is not even
  6. // close to linear.  The speedup should be close to linear since
  7. // this is an easily decomposable compute-intensive problem.
  8. //
  9. // Jeff Chase 8/15/88
  10. // University of Washington
  11. //
  12.  
  13.  
  14. #include "presto.h"
  15. #include "set.h"
  16.  
  17. #define DEFAULT_WORKERS 4
  18. #define MAXWORKERS 128
  19.  
  20. int wantedsum;
  21.  
  22. Oqueue solutions;
  23. Spinlock sol_lock;
  24. int show_solutions = 0;
  25.  
  26. Spinlock threadlock;
  27. int threadcount = 1;
  28. int wantedthreads = DEFAULT_WORKERS;
  29.  
  30. Thread *workers[MAXWORKERS];
  31.  
  32. int
  33. maxtotal(int setsize)
  34. {
  35.     int i, sum;
  36.     sum = 0;
  37.     for(i = 0; i < setsize; i++)
  38.         sum += i;
  39.     return(sum);
  40. }
  41.  
  42. void
  43. sum_of_sub(Set *s, int k, int r)
  44. {
  45.     Set *newset;
  46.     int fork, i;;
  47.  
  48.     //
  49.     // Generate left child -- include k in the set and see if 
  50.     // if it sums to wantedsum.  If yes, add to solution list.
  51.     // If we haven't started all our threads yet, fire off a
  52.     // new thread to do the rest of this subtree for us.
  53.     //
  54.  
  55.     newset = s->clone();
  56.     newset->include(k);
  57.     if (newset->sum() == wantedsum) {
  58.         sol_lock.lock();
  59.         solutions.append(newset);
  60.         sol_lock.unlock();
  61.     } else {
  62.         if (newset->sum() + k + 1 <= wantedsum) {
  63.             fork = 0;
  64.             if (threadcount < wantedthreads) {
  65.                 threadlock.lock();
  66.                 if (threadcount < wantedthreads) {
  67.                     i = threadcount++;
  68.                     fork = 1;
  69.                 }
  70.                 threadlock.unlock();
  71.             }
  72.             if (fork) {
  73.                 workers[i] = new Thread();
  74.                 workers[i]->willjoin();
  75.                 workers[i]->start(0, (PFany) sum_of_sub, newset, k+1, r-k);
  76.             } else {
  77.                 sum_of_sub(newset, k+1, r-k);
  78.             }
  79.         }
  80.     }
  81.  
  82.     //
  83.     // Generate right child.
  84.     //
  85.  
  86.     if ((s->sum() + r - k >= wantedsum)
  87.      && (s->sum() + k + 1 <= wantedsum)) {
  88.         sum_of_sub(s, k + 1, r - k);
  89.     }
  90. }
  91.  
  92. int
  93. Main::init()
  94. {
  95.     numprocessors = DEFAULT_WORKERS;
  96.     quantum = 0;
  97.     wantedsum = 23;
  98.  
  99.     for (argc--, argv++; *argv && **argv == '-'; argv++, argc--)
  100.         switch (*(*argv + 1)) {
  101. #ifdef i386
  102.                 case 'a':
  103.                         affinity = 1;
  104.                 break;
  105. #endif i386
  106.             case 'q':
  107.                 quantum = atoi(*argv + 2);
  108.                 break;
  109.             case 'n':
  110.                 numprocessors = atoi(*argv + 2);
  111.                 break;
  112.             case 's':
  113.                 wantedsum = atoi(*argv + 2);
  114.                 break;
  115.             case 't':
  116.                 wantedthreads = atoi(*argv + 2);
  117.                 break;
  118.  
  119.             case 'v':
  120.                 show_solutions = 1;
  121.                 break;
  122.             default:
  123.                 cerr << chr(*(*argv + 1)) << " unknown flag.\n";
  124.                     return -1;
  125.         }
  126.     if (wantedthreads > MAXWORKERS) {
  127.         cerr << "Too many threads.\n";
  128.         return 1;
  129.     } else
  130.         return 0;
  131. }
  132.  
  133. Main::main()
  134. {
  135.     Set *empty = new Set;
  136.     Set *s;
  137.     int sc;
  138.     Timer stopwatch;
  139.     double runtime;
  140.     int i;
  141.  
  142.     stopwatch.init();
  143.     stopwatch.timerstart();
  144.  
  145.     sum_of_sub(empty, 0, maxtotal(128));
  146.     while(threadcount < wantedthreads);
  147.     for (i = 1; i < wantedthreads; i++) {
  148.         workers[i]->join();
  149.     }        
  150.  
  151.     runtime = stopwatch.timermark();
  152.     sc = 0;
  153.     while((s = (Set *)solutions.get()) != NULL) {
  154.         sc++;
  155.         if (show_solutions)
  156.             s->print(cout);
  157.     }
  158.     cout << form("Elapsed time = %g seconds.\n", runtime);
  159.     cout << form("There are %d solutions for %d.\n", sc, wantedsum);
  160.     cout.flush();
  161. }
  162.  
  163.  
  164.